/**
 * 在第一行我们写上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
 * 给定行数N和序数 K，返回第 N 行中第 K个字符。（K从1开始）
 *
 * 例子:
 *
 * 输入: N = 1, K = 1
 * 输出: 0
 *
 * 输入: N = 2, K = 1
 * 输出: 0
 *
 * 输入: N = 2, K = 2
 * 输出: 1
 *
 * 输入: N = 4, K = 5
 * 输出: 1
 *
 * 解释:
 * 第一行: 0
 * 第二行: 01
 * 第三行: 0110
 * 第四行: 01101001
 *
 * 注意：
 * N的范围[1, 30].
 * K的范围[1, 2^(N-1)].
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/k-th-symbol-in-grammar
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q00779m {
    public int kthGrammar(int n, int k) {
        boolean[] evens = new boolean[32];
        int idx = 0;
        while (k != 1) {
            evens[idx++] = (k & 1) == 0;
            k = (k + 1) / 2; // 由最接近的偶数折半而生成
        }
        int ans = 0;
        while (--idx >= 0) {
            if (evens[idx]) {
                ans = 1 - ans;
            }
        }
        return ans;
    }
}
